import java.util.*;

class Student{
    public String name;
    public int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
}
public class Main {
    public static void main(String[] args) {
        char[]ch = new char[]{'a','b','c'};
        String s1 = new String(ch);
        s1.intern();
        String s2 ="abc";
        System.out.println(s1 == s2);
    }
    public static void main2(String[] args) {
        Student s1 = new Student("zhangsan",10);
        Student s2 = new Student("zhangsan",10);
        System.out.println(s2==s1);
        String s3 = new String("haha");
        String s4 = new String("haha");
        System.out.println(s3==s4);
        String s5 = "haha";
        String s6 = "haha";
        System.out.println(s5==s6);
    }
    public static void main1(String[] args) {
        String s1 = "Hello world!";
        s1 = "xixi";
        System.out.println(s1);
    }
    public int countSegments(String s) {
        String[] ret = s.split(" |,");
        return ret.length;
    }

    /**
     * 1.两数之和
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] ret = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int n = target - nums[i];
            if(map.containsKey(n)){
                ret[0] = i;
                ret[1] = map.get(n);
                return ret;
            }else{
                map.put(nums[i],i);
            }
        }
        return ret;
    }

    /**
     * 2.字母异位词分组
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,List<String>> map = new HashMap<>();
        List<List<String>> ret = new ArrayList<>();
        for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            if(map.containsKey(chars.toString())){
                map.get(chars).add(strs[1]);
            }else {
                map.put(chars.toString(),new ArrayList<>());
            }

        }
        return new ArrayList<>(map.values());
    }

    /**
     * 盛最多水的容器
     */
        public int maxArea(int[] height) {
            int left = 0;
            int right = height.length-1;
            int max = 0;
            while(left<=right){
                int v = Math.min(height[left],height[right])*(right-left);
                if(max<v) max=v;

                if (height[left] <= height[right]) {
                    left++;
                } else {
                    right--;
                }

            }

            return max;
        }

    /**
     * https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/
     * 滑动窗口
     * @param nums
     * @param x
     * @return
     */
        public int minOperations(int[] nums, int x) {
            int left = 0;
            int right = 0;
            int sum = 0;
            for(int num:nums) sum+=num;
            int target = sum-x;
            int sum2 = 0;
            int ret = -1;
            if (target == 0) return nums.length;
            if (target < 0) return -1;
            while(right<nums.length){
                sum2+=nums[right];
                while(sum2>target){
                    sum2-=nums[left];
                    left++;
                }
                if(target==sum2){
                    ret = Math.max(ret,right-left+1);
                }

                right++;

            }
            return ret != -1 ? nums.length - ret : -1;}
    /**
     * 面试题 02.04. 分割链表
     * https://leetcode.cn/problems/partition-list-lcci/
     */
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }}
    public ListNode partition(ListNode head, int x) {
        ListNode smallhead = new ListNode();
        ListNode largehead = new ListNode();
        ListNode small = smallhead;
        ListNode large = largehead;
        while(head!=null){
            if(head.val>=x){
                large.next = head;
                large = large.next;
            }else{
                small.next = head;
                small = small.next;
            }
            head = head.next;
        }
        large.next = null;
        small.next = largehead.next;
        return smallhead.next;
    }
    public class TreeNode {
     int val;
      TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
  }

    /**
     *https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
     * 将有序数组转化为二叉搜索树
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = treeval(nums,0,nums.length - 1);
        return root;
    }
    //选取区间为左闭右闭
    TreeNode treeval(int[] nums,int left,int right){
        if(left>right){
            return null;
        }
        int mid = (left+right)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = treeval(nums,left,mid-1);
        root.right = treeval(nums,mid+1,right);

        return root;
    }

    /**
     * https://leetcode.cn/problems/merge-intervals/
     * 合并区间
     * 1.先排序
     * 2.发现规律：有重叠后区间左小于等于前区间右
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        //按左端点排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> ret = new ArrayList();
        int left = intervals[0][0],right = intervals[0][1];
        for(int i = 1;i<intervals.length;i++){
            int a = intervals[i][0],b = intervals[i][1];
            if(a<=right)//有重叠
            {
                right = Math.max(b,right);
            }
            else{
                ret.add(new int[]{left,right});
                left = a;
                right = b;
            }
        }
        ret.add(new int[]{left,right});

        return ret.toArray(new  int[0][]);
    }

    /**
     * 前缀和
     *DP34 【模板】前缀和
     */
        public void main1() {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
            int[] arr = new int[n+1];
            for(int i = 1;i<n+1;i++){
                arr[i] = in.nextInt();
            }

            //初始化前缀和数组
            long[]dp = new long[n+1];
            dp[0] = 0;
            for(int i = 1;i<n+1;i++){
                dp[i] = dp[i-1] + arr[i];
            }
            while(in.hasNext()){
                int l = in.nextInt();
                int r = in.nextInt();
                System.out.println(dp[r]-dp[l-1]);
            }

        }

    /**
     * 560. 和为 K 的子数组
     * https://leetcode.cn/problems/subarray-sum-equals-k/
     * 利用前缀和＋哈希表
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        //key 前缀和 value 出现的次数
        map.put(0,1);
        int sum = 0,ret =0;
        for(int num:nums){
            sum = sum + num;
            ret += map.getOrDefault(sum-k,0);
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return ret;
    }

    /**
     525. 连续数组
     https://leetcode.cn/problems/contiguous-array/
     * @param nums
     * @return
     */
    public int findMaxLength(int[] nums) {
        int ret = 0,sum = 0;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        map.put(0,-1);
        for(int i = 0;i<nums.length;i++){
            if(nums[i]==0){
                sum+=-1;
            }else{
                sum+=1;
            }
            if(map.containsKey(sum)){
                ret = Math.max(ret, i - map.get(sum));
            }

            else{
                map.put(sum,i);
            }
        }
        return ret;
    }
    /**
     * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
     * 106.中序后序构造二叉树
     */
    public int i = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        i = postorder.length - 1;
        int ib = 0;
        int ie = inorder.length - 1;
        int pi = 0;
        return buildTreeChild(inorder,postorder,pi,ib,ie);
    }
    public TreeNode buildTreeChild(int[] inorder,int[] postorder,int pi,int ib,int ie) {
        if(ib>ie){
            return null;
        }
        TreeNode root = new TreeNode(postorder[i]);
        pi = find(inorder,ib,ie,root.val);
        i--;
        root.right = buildTreeChild(inorder,postorder,pi,pi+1,ie);
        root.left = buildTreeChild(inorder,postorder,pi,ib,pi-1);
        return root;
    }

    private int find(int[] inorder,int ib,int ie,int val){
        for(int j = ib;j<=ie;j++){
            if(inorder[j] == val){
                return j;
            }
        }
        return -1;
    }
    /**
     * https://leetcode.cn/problems/copy-list-with-random-pointer/
     * 138 随机链表的复制
     */

    /**
     * 翻转二叉树
     */
    public TreeNode invertTree(TreeNode root) {
        if(root==null){
            return null;
        }
        TreeNode t;
        t = root.left;
        root.left = root.right;
        root.right = t;

        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
    /**
     * LCR 019. 验证回文串 II
     * https://leetcode.cn/problems/RQku0D/
     */
    public boolean validPalindrome(String s) {
        int left = 0,right = s.length()-1;
        while(left<right){
            if(s.charAt(left)!=s.charAt(right)){
                return isPalindrome(s,left+1,right)||isPalindrome(s,left,right-1);
            }
            left++;
            right--;
        }
        return true;
    }
    public boolean isPalindrome(String s,int start,int end){
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    /**
     * 611. 有效三角形的个数
     * https://leetcode.cn/problems/valid-triangle-number/
     */
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int big ,ret = 0;
        for(big = nums.length - 1;big>0;big--){
            int left = 0,right = big-1;
            while(left<right){
                if(nums[left]+nums[right]>nums[big]){
                    ret+=right-left;
                    right--;
                } else{
                    left++;
                }
            }
        }
        return ret;
    }

    /**
     * LCR 179. 查找总价格为目标值的两个商品
     * https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
     * @param price
     * @param target
     * @return
     */
        public int[] twoSum2(int[] price, int target) {
            //有序 利用双指针＋单调性
            int left = 0,right = price.length-1;
            while(left<right){
                if(price[left]+price[right]==target){
                    return new int[] {price[left],price[right]};
                }else if(price[left]+price[right]>target){
                    right--;
                }else{
                    left++;
                }
            }

            return null;
        }
    /**
     *https://leetcode.cn/problems/3sum/
     * 三数之和
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new LinkedList();
        for(int i = 0;i<nums.length;i++){
            if(nums[i]>0){
                break;
            }
            if(i!=0&&nums[i] == nums[i-1]){
                continue;
            }
            int left = i+1,right = nums.length - 1;
            while(left<right){
                if(nums[left]+nums[right]<-nums[i]){
                    left++;
                }else if(nums[left]+nums[right]>-nums[i]){
                    right--;
                }else{
                    ret.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left-1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right+1]) {
                        right--;
                    }
                }
            }
        }
        return ret;

    }
    /**
     * 四数之和
     * https://leetcode.cn/problems/4sum/
     */
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> ret = new ArrayList();
            Arrays.sort(nums);
            int n = nums.length;
            if (n < 4) {
                return ret;
            }
            for(int i = 0;i<n-3;i++){
                if(i!=0&&nums[i]==nums[i-1]) continue;
                // 剪枝优化
                // a. 当前i所能组成的最小和都大于target，后续i更大，和会更大，直接break
                if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                    break;
                }
                // b. 当前i和最后三个数的和都小于target，当前i太小，跳过
                if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
                    continue;
                }

                for(int j = i+1;j<n-2;j++){
                    if(j!=i+1&&nums[j]==nums[j-1]) continue;
                    int left = j+1;
                    int right = n-1;
                    long tj = (long)target-nums[i]-nums[j];
                    while(left<right){
                        int sum =nums[left]+nums[right];
                        if(sum<tj) left++;
                        else if(sum>tj) right--;
                        else{
                            ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                            left++;
                            right--;
                            while(left<right&&nums[left]==nums[left-1]) left++;
                            while(left<right&&nums[right]==nums[right+1]) right--;
                        }
                    }


                }
            }

            return ret;
        }
        /**
         *
         */
        class Node {
            public int val;
            public List<Node> _children;

            public Node() {}

            public Node(int _val) {
                val = _val;
            }

            public Node(int _val, List<Node> _children) {
                val = _val;
                this._children = _children;
            }
        };
        public List<List<Integer>> levelOrder(Node root) {
            Queue<Node> queue = new LinkedList();
            List<List<Integer>> ret = new LinkedList();
            if(root==null) return ret;
            queue.offer(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                List<Integer> curList = new LinkedList();
                while(size>0){
                    size--;
                    Node cur = queue.poll();
                    curList.add(cur.val);
                    if(cur._children!=null&&!cur._children.isEmpty()){
                        queue.addAll(cur._children);
                    }
                }
                ret.add(curList);
            }
            return ret;
        }

















































}




